#include <bitset>
#include <cstring>
#include <iostream>
#include <algorithm>

using ll = long long;

struct ReadLL{
    char c;
    ll w,n;
    ReadLL&operator>>(ll &num){
        c=0,w=1,n=0;
        while(!isdigit(c)){
            if(c=='-')w=-1;
            c=getchar();
        }
        while(isdigit(c)){
            n=n*10+c-'0';
            c=getchar();
        }
        num=n*w;
        return *this;
    }
}readll;

auto &is = readll;
auto &os = std::cout;

const ll max_n{100+5},max_a=2.5e4+5;
ll t, n, a[max_n], ans;
std::bitset<max_a> dp;

int main(){
    is>>t;
    for(ll _{0};_<t;_++){
        is>>n;
        ans=n;
        for(ll i{1};i<=n;i++){
            is>>a[i];
        }
        std::sort(a+1,a+n+1);
        dp.reset();
        dp[0]=1;
        for(ll i{1};i<=n;i++){
            if(dp[a[i]]){
                ans--;
                continue;
            }
            for(ll j{a[i]};j<=a[n];j++){
                dp[j]=dp[j]||dp[j-a[i]];
            }
        }
        os<<ans<<'\n';
    }
}